/// \file
/// The source file containing the solver class implementation that aren't
/// templated.
/// \par Subversion URI:
/// \$URL: http://doku.googlecode.com/svn/trunk/src/solver.cpp $
/// \version \$Rev: 27 $
/// \date    \$Date: 2012-03-19 20:24:11 +0000 (Mon, 19 Mar 2012) $

#include "solver.hpp"

using namespace std;

namespace solver
{
	//////////////////////////////////////////////////////////////////////////
	void Parent::AddChild(Child *child) {
		AddMember(child);
		child->AddMember(this);
	}

	void Parent::RecvExcludeUp(unsigned short x, const Child *sender) {
		for (unsigned i = 0; i < nmembers; i++)
			if (members[i] != sender)
				members[i]->RecvExcludeDown(x, sender);
	}

	unsigned short Parent::GetSum() const {
		unsigned short sum = 0;
		for (unsigned i = 0; i < nmembers; i++)
			sum |= members[i]->GetField();
		return sum;
	}

	void Parent::Eliminate(unsigned short set) {
		unsigned short found1 = 0, found2 = 0;
		for (unsigned i = 0; i < nmembers; i++) {
			const unsigned short f = members[i]->GetField();
			found2 |= found1 & f;
			found1 |= f;
		}
		found1 &= ~found2 & set;
		if (found1) {
			for (unsigned i = 0; i < nmembers; i++) {
				const unsigned short f = members[i]->GetField() & found1;
				if (f && !members[i]->IsResolved())
					members[i]->Resolve(f);
			}
		}
	}

	bool Parent::IsValid() const {
		unsigned short found = 0;
		for (unsigned i = 0; i < nmembers; i++) {
			const unsigned short field = members[i]->GetField();
			if (field & found)
				return false;
			found |= field;
		}
		return true;
	}

	//////////////////////////////////////////////////////////////////////////
	void Cell::Resolve(unsigned short x) {
		if (!x)
			board->MarkUnsolvable();
		else {
			board->IncrementSolved();
			field = x;
			Child::Resolve(x);
		}
	}

	void Cell::DoExclusion(unsigned short x, const Child *sender) {
		field &= ~x;
		if (!field)
			board->MarkUnsolvable();
	}

	//////////////////////////////////////////////////////////////////////////

	unsigned Board::solutions = 0;

	Board::Board(const Board &copy) : lincells(cells[0][0][0]) {
		resolvedcells = copy.resolvedcells;
		solvable = copy.solvable;
		SetLinks();

		for (unsigned i = 0; i < NCELLS; i++)
			lincells[i].Copy(copy.lincells[i]);
		for (unsigned i = 0; i < N*N*N; i++) {
			subrows[0][0][i].Copy(copy.subrows[0][0][i]);
			subcols[0][0][i].Copy(copy.subcols[0][0][i]);
		}
	}

	void Board::SetLinks() {
		for (unsigned Y = 0; Y < N; Y++)
			for (unsigned y = 0; y < N; y++)
				for (unsigned X = 0; X < N; X++)
					rows[Y][y].AddChild(&subrows[Y][X][y]);
		for (unsigned X = 0; X < N; X++)
			for (unsigned x = 0; x < N; x++)
				for (unsigned Y = 0; Y < N; Y++)
					cols[X][x].AddChild(&subcols[Y][X][x]);
		for (unsigned Y = 0; Y < N; Y++) {
			for (unsigned X = 0; X < N; X++) {
				for (unsigned y = 0; y < N; y++) {
					boxrows[Y][X].AddChild(&subrows[Y][X][y]);
					for (unsigned x = 0; x < N; x++) {
						subrows[Y][X][y].AddChild(&cells[Y][y][X][x]);
						cells[Y][y][X][x].SetBoard(this);
					}
				}
				for (unsigned x = 0; x < N; x++) {
					boxcols[Y][X].AddChild(&subcols[Y][X][x]);
					for (unsigned y = 0; y < N; y++)
						subcols[Y][X][x].AddChild(&cells[Y][y][X][x]);
				}
			}
		}
	}

	void Board::InitFromStream(std::istream &in) {
		Cell *cell = &cells[0][0][0][0], *const stop = cell + NCELLS;
		for (; cell != stop; cell++) {
			char c;
			in >> c;
			if (c >= '1' && c <= '9')
				cell->Init(c);
		}
	}

	void Board::Eliminate() {
		unsigned oldrc;
		do {
			oldrc = resolvedcells;
			for (unsigned Y = 0; Y < N; Y++)
				for (unsigned y = 0; y < N; y++)
					rows[Y][y].Eliminate();
			for (unsigned X = 0; X < N; X++)
				for (unsigned x = 0; x < N; x++)
					cols[X][x].Eliminate();
			for (unsigned Y = 0; Y < N; Y++) {
				for (unsigned X = 0; X < N; X++) {
					boxrows[Y][X].Eliminate();
					boxcols[Y][X].Eliminate();
				}
			}
			if (resolvedcells >= NCELLS)
				return;
		} while (oldrc != resolvedcells);
	}

	void Board::FinishSolve(std::ostream &out) {
		Eliminate();
		if (resolvedcells == NCELLS) {
			out << endl << "Unique solution, no guesswork needed:" << endl;
			Output(out);
			out << endl;
		}
		else {
			out << endl << "Before guesswork:" << endl;
			Output(out);
			out << endl;
			SolveRecurse(out, 0);
		}
	}

	void Board::SolveRecurse(std::ostream &out, unsigned startcell, unsigned depth) {
		if (IsSolvable()) {
			if (resolvedcells != NCELLS) {
				Guess(out, startcell, depth);
				return;
			}
			if (IsValid()) {
				switch (solutions) {
				case 0:
					out << "First solution:" << endl << endl;
					Output(out);
					break;
				case 1:
					out << "Other solutions:" << endl << endl;
				default:
					Output(out, true);
				}
				solutions++;
				return;
			}
		}
		if (!startcell) {
			out << "No complete solutions." << endl << endl;
			Output(out);
		}
	}

	void Board::Guess(std::ostream &out, unsigned startcell, unsigned depth) const {
		for (;; startcell++) {
			if (startcell == NCELLS)
				return;
			if (!lincells[startcell].IsResolved())
				break;
		}

		const unsigned row = startcell/(N*N),
			col = startcell%(N*N);

		const unsigned short field = lincells[startcell].GetField();
		for (unsigned short res = 1, i = 1; res <= field; res <<= 1, i++) {
			if (field & res) {
				for (unsigned s = 0; s < depth; s++) out << ' ';
				out << "Trying (" << row << ',' << col << ")=" << i << endl;
				Board copy(*this);
				copy.lincells[startcell].Resolve(res);
				copy.Eliminate();
				copy.SolveRecurse(out, startcell+1, depth+1);
			}
		}
	}

	void Board::Output(std::ostream &out, bool line) const {
		if (line) {
			for (unsigned i = 0; i < NCELLS; i++)
				out << lincells[i].GetChar();
		}
		else {
			out << "=====================================" << endl;
			for (unsigned Y = 0; Y < N; Y++) {
				for (unsigned y = 0; y < N; y++) {
					if (resolvedcells == NCELLS) {
						for (unsigned X = 0; X < N; X++) {
							for (unsigned x = 0; x < N; x++)
								out << cells[Y][y][X][x].GetChar();
							out << ' ';
						}
					}
					else for (unsigned p = 0; p < N; p++) {
						for (unsigned X = 0; X < N; X++) {
							for (unsigned x = 0; x < N; x++) {
								cells[Y][y][X][x].Output(out, p);
								out << ' ';
							}
							out << ' ';
						}
						out << endl;
					}
					out << endl;
				}
				out << endl;
			}
		}
		out << endl;
	}

	bool Board::IsValid() const {
		for (unsigned i = 0; i < N; i++)
			for (unsigned j = 0; j < N; j++)
				if (!(rows[i][j].IsValid() &&
					cols[i][j].IsValid() &&
					boxrows[i][j].IsValid() &&
					boxcols[i][j].IsValid()))
					return false;
		return true;
	}
}
